Non-volatile memory systems, such as flash memory, have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device.
Some flash memory management systems employ self-caching architectures for data buffering and data caching. For example, caching may be used for data buffering where data received from the host device is first stored in a portion of the memory designated as the cache and is later copied to a portion of the flash memory designated as a main storage area (such as a multi-level cell (MLC) type flash memory). As another example, caching may be used for control data storage to improve operation time. Control data may include mapping tables and other memory management data used by in the flash memory.
When a host device requests data from, or writes data to, a flash memory, the host read request includes logical address information that the flash memory must then map to physical flash memory addresses. As part of this mapping process, multiple mapping table (also referred to as control data) lookups are typically necessary. For example, the flash memory system may have data organized such that fragments of logical groups are stored in a cache area of flash memory and the remainder of the logical group associated with the data request is in main storage in the flash memory.
A typical way in which the flash memory will search for data associated with a host request is to always first check for possible logical group fragments in a secondary table that tracks logical group fragments in the cache and then search for the logical group information in a primary table in main storage. However, there may be many instances where there are no logical group fragments in the cache associated with the requested data. In these instances, checking the secondary index for entries on relevant logical group fragments will result in a “miss” where no result will be returned because no logical group fragments relating to the logical group are present. When the number of logical fragments are few, the process of always retrieving and parsing the secondary table that tracks logical group fragments in the cache, prior to then retrieving and parsing a primary table, can lead to many misses in the secondary table. The time necessary to retrieve and parse the secondary table is then wasted and may slow down overall flash performance.